package com.body.park.user.bloom;

import com.google.common.hash.Funnel;
import com.google.common.hash.Funnels;
import com.google.common.hash.Hashing;

import java.nio.charset.Charset;

/**
 * @Author chaoxian.wu
 * @DATE 2022/4/20 9:18
 * Bloom Filter的核心类
 */
public class BloomFilterHelper<T> {

    /**
     * 定义hash函数执行次数
     */
    private int numHashFunctions;
    /**
     * bit数组大小
     */
    private int bitSize;
    /**
     * 数据类型
     */
    private Funnel<T> funnel;

    /**
     * 设置默认的误判率
     */
    private static final double errorRatio = 0.02;

    /**
     * 无参构造器
     */
    public BloomFilterHelper() {

    }

    /**
     * 构造方法
     * @param insertions 需要插入的数据条数
     */
    public BloomFilterHelper(int insertions) {
        this.funnel = (Funnel<T>) Funnels.stringFunnel(Charset.defaultCharset());
        bitSize = optimalBitsLength(insertions, errorRatio);
        numHashFunctions = optimalHashFunctionsCnt(insertions, bitSize);
    }

    /**
     * 构造方法
     *
     * @param funnel 数据类型
     * @param insertions 插入的数据条数
     * @param errorRatio 误判率
     */
    public BloomFilterHelper(Funnel<T> funnel, int insertions, double errorRatio) {
        this.funnel = funnel;
        bitSize = optimalBitsLength(insertions, errorRatio);
        numHashFunctions = optimalHashFunctionsCnt(insertions, bitSize);
    }

    /**
     * hash计算
     * 计算多次hash对应的下标
     *
     * @param value 需要hash的值
     * @return 偏移量数组
     */
    public int[] offsetArray(T value) {
        int[] offset = new int[numHashFunctions];
        long hash64 = Hashing.murmur3_128().hashObject(value, funnel).asLong();
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);
        for (int i = 1; i <= numHashFunctions; i++) {
            int nextHash = hash1 + i * hash2;
            if (nextHash < 0) {
                nextHash = ~nextHash;
            }
            offset[i - 1] = nextHash % bitSize;
        }
        return offset;
    }

    /**
     * 计算最佳的bit数组长度
     *
     * @param insertions 需要插入的数据总数
     * @param errorRatio 误判率
     * @return bit数组长度
     */
    private int optimalBitsLength(long insertions, double errorRatio) {
        if (errorRatio == 0) {
            errorRatio = 0.03;
        }
        return (int) (-insertions * Math.log(errorRatio) / (Math.log(2) * Math.log(2)));
    }

    /**
     * 计算hash方法执行的最佳次数
     *
     * @param insertions 插入数据总数
     * @param bitSize bit数组大小
     * @return 最佳hash次数
     */
    private int optimalHashFunctionsCnt(long insertions, long bitSize) {
        return Math.max(1, (int) Math.round((double) bitSize / insertions * Math.log(2)));
    }
}
